package mo.offer_special;

public class L093 {

    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        int max = 0;
        int[][] dp = new int[n][n];
        for (int i = 2; i < n; i++) {
            int j = 0;
            int k = i - 1;
            while (j < k) {
                if (arr[j] + arr[k] == arr[i]) {
                    if (dp[j][k] == 0) {
                        dp[k][i] = 3;
                    } else {
                        dp[k][i] = dp[j][k]+ 1;
                    }
                    max = Math.max(max, dp[k][i]);
                    j++;
                    k--;
                } else if (arr[j] + arr[k] < arr[i]) {
                    j++;
                } else {
                    k--;
                }

            }
        }
        return max;
    }

}
